package com.topcoder.srm194;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class IslandFerries {
	private int INF = 40000;
	private int I;
	private int S;
	private int[][]	costs;
	private int[][] prices;
	private boolean[][][] path;
	private PriorityQueue<State> pq;
	
	public int[] costs(String[] legs, String[] prices) {
		I = prices.length;		// island number, at most 40
		S = legs.length;		// service number, at most 10
		int MAX = 1 << S;		// maximum cost
		costs = new int[I][MAX];
		for (int i=0; i<I; i++) {
			Arrays.fill(costs[i], INF);
		}
		
		this.prices = new int[I][S];
		for (int i=0; i<I; i++) {
			String[] t = prices[i].split(" ");
			for (int j=0; j<S; j++) {
				this.prices[i][j] = Integer.parseInt(t[j]);
			}
		}
		
		path = new boolean[S][I][I];
		for (int i=0; i<S; i++) {
			StringTokenizer st = new StringTokenizer(legs[i], "- ");
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				path[i][from][to] = true;
			}
		}
		
		pq = new PriorityQueue<State>(10, new Comparator<State>(){
			public int compare(State a, State b) {
				return a.cost - b.cost; 
			}
		});
		pq.add(new State(0, 0, 0));
		
		while (!pq.isEmpty()) {
			State s = pq.remove();
			if (costs[s.island][s.tickets] >= s.cost) {
				buyTicket(s.island, s.tickets, s.cost);
				useTicket(s.island, s.tickets, s.cost);
			}
		}
		
		int[] res = new int[I-1];
		for (int i=0; i<I-1; i++) res[i] = costs[i+1][0]==INF? -1 : costs[i+1][0];
		return res;
	}
	
	private void buyTicket(int island, int tickets, int cost) {
		if (count(tickets) >= 3) return;
		for (int service=0; service<S; service++) {
			if ((tickets & (1<<service)) > 0) continue;
			int newTickets = tickets | (1 << service);
			int newCost = cost + prices[island][service];
			
			if (costs[island][newTickets] > newCost) {
				pq.add(new State(island, newTickets, newCost));
				costs[island][newTickets] = newCost;
			}
		}
	}
	
	private void useTicket(int from, int tickets, int cost) {
		for (int service=0; service<S; service++) {
			if ((tickets & (1 << service)) == 0) continue;
			int newTickets = tickets & ~(1 << service);
			for (int to=0; to<I; to++) {
				if (path[service][from][to] && costs[to][newTickets] > cost) {
					pq.add(new State(to, newTickets, cost));
					costs[to][newTickets] = cost;
				}
			}
		}
	}
	
	private int count(int tickets) {
		int count = 0;
		while (tickets > 0) {
			tickets = tickets & (tickets - 1);
			count++;
		}
		return count;
	}
	
	private class State {
		int island;
		int tickets;
		int cost;
		public State(int island, int tickets, int cost) {
			this.island = island;
			this.tickets = tickets;
			this.cost = cost;
		}
	}
}
